#!/usr/bin/python3
# -*- coding:utf-8 -*-
# __author__ == taoyulong2018@gmail.com
# __time__ == 2023/6/30 11:03
# ===========================================
#       题目名称： 63. 不同路径 II
#       题目地址： https://leetcode.cn/problems/unique-paths-ii/
#       题目描述： https://note.youdao.com/s/LWYgPSzT
# ===========================================


class Solution:

    def uniquePathsWithObstacles(self, obstacleGrid):
        """
            通过动态规划实现
        """
        m = len(obstacleGrid)
        n = len(obstacleGrid[0])

        # 创建二维数组dp，并初始化值为0
        dp = [[0] * n for _ in range(m)]

        # 初始化第一行和第一列的值
        for i in range(m):
            if obstacleGrid[i][0] == 1:
                break
            dp[i][0] = 1

        for j in range(n):
            if obstacleGrid[0][j] == 1:
                break
            dp[0][j] = 1

        # 遍历整个数组，更新dp值
        for i in range(1, m):
            for j in range(1, n):
                if obstacleGrid[i][j] == 1:
                    dp[i][j] = 0
                else:
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1]

        # 返回终点的路径数
        return dp[m - 1][n - 1]

    def uniquePathsWithObstacles3(self, obstacleGrid):
        """
            用一个不重复的集合记录 走的每一步
            超出时间限制
        """
        import time
        s = time.time()
        count = 0  # 当前可能性
        start, end = (0, 0), (len(obstacleGrid) - 1, len(obstacleGrid[0]) - 1)  # 起始位置, 结束位置
        steps = [[start]]  # 定义步数集合 [[(第一步),(第二步),....], ]
        while steps and obstacleGrid[0][0] != 1:
            temp_steps = []
            for step in steps:
                x, y = step[-1]  # 当前最后一步走的位置
                print("count => %d steps => %d x => %d y => %d 消耗时间：%d" % (count, len(steps), x, y, time.time() - s))
                if obstacleGrid[x][y] != 1 and x == len(obstacleGrid) - 1 and y == len(obstacleGrid[0]) - 1:
                    count += 1
                    continue
                # 向右走
                if y + 1 >= len(obstacleGrid[x]):
                    if x + 1 >= len(obstacleGrid):
                        pass
                    else:
                        if obstacleGrid[x + 1][y] != 1:
                            temp_step = step.copy()
                            temp_step.append((x + 1, y))
                            temp_steps.append(temp_step)
                else:
                    if obstacleGrid[x][y + 1] != 1:
                        temp_step = step.copy()
                        temp_step.append((x, y + 1))
                        temp_steps.append(temp_step)
                # 向下走
                if x + 1 >= len(obstacleGrid):
                    if y + 1 >= len(obstacleGrid[x]):
                        pass
                    else:
                        if obstacleGrid[x][y + 1] != 1:
                            temp_step = step.copy()
                            temp_step.append((x, y + 1))
                            temp_steps.append(temp_step)
                else:
                    if obstacleGrid[x + 1][y] != 1:
                        temp_step = step.copy()
                        temp_step.append((x + 1, y))
                        temp_steps.append(temp_step)

            steps = [x for i, x in enumerate(temp_steps) if x not in temp_steps[:i]]  # 去重

        return count

    def uniquePathsWithObstacles2(self, obstacleGrid):
        """
            实现的有问题
        """
        count = 0
        routes = [[(0, 0)]]  # 定义路线   [路线可能性1，。。。。 n]
        while routes:
            temp_routes = []
            for route in routes:
                x, y = route[-1]  # 最后的一步
                # 向左
                if y + 1 > len(obstacleGrid[x]) - 1:
                    if x + 1 > len(obstacleGrid) - 1:
                        pass
                    else:
                        if obstacleGrid[x + 1][y] != 1:
                            temp_route = route.copy()
                            temp_route.append((x + 1, y))
                            temp_routes.append(temp_route)
                else:
                    if obstacleGrid[x][y + 1] != 1:
                        temp_route = route.copy()
                        temp_route.append((x, y + 1))
                        temp_routes.append(temp_route)
                # 向下
                if x + 1 > len(obstacleGrid) - 1:
                    if y + 1 > len(obstacleGrid[x]) - 1:
                        pass
                    else:
                        if obstacleGrid[x][y + 1] != 1:
                            temp_route = route.copy()
                            temp_route.append((x, y + 1))
                            temp_routes.append(temp_route)
                else:
                    if obstacleGrid[x + 1][y] != 1:
                        temp_route = route.copy()
                        temp_route.append((x + 1, y))
                        temp_routes.append(temp_route)
            # 去重
            temp_routes = {tuple(item) for item in temp_routes}
            temp_routes = list(list(item) for item in temp_routes)
            cur_index = 0

            while cur_index < len(temp_routes):
                temp_route = temp_routes[cur_index]
                if (len(obstacleGrid) - 1, len(obstacleGrid[0]) - 1) in temp_route:
                    count += 1
                    del temp_routes[cur_index]
                else:
                    cur_index += 1
            routes = temp_routes
        return count


if __name__ == '__main__':
    s = Solution()
    # 2
    print("obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]] => ", s.uniquePathsWithObstacles(obstacleGrid=[[0, 0, 0], [0, 1, 0], [0, 0, 0]]))
    # 1
    print("obstacleGrid = [[0,1],[0,0]] => ", s.uniquePathsWithObstacles(obstacleGrid=[[0, 1], [0, 0]]))
    # 0
    print("obstacleGrid = [[1]] => ", s.uniquePathsWithObstacles(obstacleGrid=[[1]]))

    print(
        s.uniquePathsWithObstacles(obstacleGrid=[[0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0], [1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 1], [0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0], [0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0], [1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0], [0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0], [0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0], [0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0], [0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1], [0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1],
                                                 [1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0], [0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 0, 1, 1, 0], [0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 1, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0], [0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0], [0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1], [0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0], [1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0], [1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1], [1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0]]))
